home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / symb_lib / adap_iso.c next >
Encoding:
C/C++ Source or Header  |  1995-02-14  |  22.2 KB  |  656 lines
  1. /******************************************************************************
  2. * Adap_iso.c - adaptive isoline surface extraction algorithm.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Aug. 92.                          *
  5. ******************************************************************************/
  6.  
  7. #include "symb_loc.h"
  8.  
  9. #define SIMILAR_PARAM_VAL    1e-4
  10.  
  11. #define CONVEX_BLEND(v1, v2, b1, b2, t) { \
  12.         CagdRType \
  13.             Blend = -b1 / ( b2 - b1 ); \
  14.         t = v2 * Blend + v1 * (1.0 - Blend); \
  15.         }
  16.  
  17. static int MinSubdivLevel = 1;
  18.  
  19. static CagdCrvStruct *SymbAdapIsoExtractAux(int Level,
  20.                         CagdSrfStruct *Srf,
  21.                         CagdSrfStruct *NSrf,
  22.                         SymbAdapIsoDistSqrFuncType
  23.                                           AdapIsoDistFunc,
  24.                         CagdCrvStruct *Crv1,
  25.                         CagdCrvStruct *NCrv1,
  26.                         CagdCrvStruct *Crv2,
  27.                         CagdCrvStruct *NCrv2,
  28.                         CagdRType Crv1Param,
  29.                         CagdRType Crv2Param,
  30.                         CagdSrfDirType Dir,
  31.                         CagdRType Eps2,
  32.                         CagdBType FullIso,
  33.                         CagdBType SinglePath);
  34. static CagdCrvStruct *CopyRegionFromCrv(CagdCrvStruct *Crv,
  35.                     CagdRType TMin,
  36.                     CagdRType TMax);
  37. static CagdRType ComputeMidParam(CagdRType Param1,
  38.                  CagdRType Param2,
  39.                  CagdSrfDirType Dir,
  40.                  CagdSrfStruct *Srf);
  41.  
  42. /*****************************************************************************
  43. * DESCRIPTION:                                                               M
  44. * Sets minimum level of subdivision forced in the adaptive iso extraction.   M
  45. *                                                                            *
  46. * PARAMETERS:                                                                M
  47. *   MinLevel:    At least that many subdivision will occur.                  M
  48. *                                                                            *
  49. * RETURN VALUE:                                                              M
  50. *   void                                                                     M
  51. *                                                                            *
  52. * KEYWORDS:                                                                  M
  53. *   SymbSetAdapIsoExtractMinLevel, adaptive isocurves                        M
  54. *****************************************************************************/
  55. void SymbSetAdapIsoExtractMinLevel(int MinLevel)
  56. {
  57.     MinSubdivLevel = MinLevel;
  58. }
  59.  
  60. /*****************************************************************************
  61. * DESCRIPTION:                                                               M
  62. * Extracts a valid coverage set of isolines from the given surface in the    M
  63. * given direction and epsilon.                             M
  64. *   If FullIso is TRUE, all extracted isocurves are spanning the entire      M
  65. * parametric domain.                                 M
  66. *   If SinglePath is TRUE, the entire coverage is going to be a single       M
  67. * curve.                                     M
  68. *   If NSrf != NULL, every second curve will be a vector field curve         M
  69. * representing the unnormalized normal for the previous Euclidean curve.     M
  70. * This mode disable the SinglePath mode.                     M
  71. *   See also function SymbSetAdapIsoExtractMinLevel.                 M
  72. *                                                                            *
  73. * PARAMETERS:                                                                M
  74. *   Srf:        To compute adaptive isocurve coverage form                   M
  75. *   NSrf:       Normal vector field defining the normals of Srf.             M
  76. *   AdapIsoDistFunc: Optional function to invoke with the two adjacent       M
  77. *        isoparametric curves of the coverage to evaluate the         M
  78. *        distance between them.                         M
  79. *   Dir:        Direction of adaptive isocurve extraction. Either U or V.    M
  80. *   Eps:        Tolerance of adaptive isocurve cuverage. For every point P   M
  81. *               on Srf there will be a point Q in one of the extracted       M
  82. *               isocurves such the |P - Q| < Eps.                 M
  83. *   FullIso:    Do we want all isocurves to span the entire domain?          M
  84. *   SinglePath: Do we want a single curve through them all?                  M
  85. *                                                                            *
  86. * RETURN VALUE:                                                              M
  87. *   CagdCrvStruct *:  A list of curves representing the computed adaptive    M
  88. *                     isocurve coverage for surface Srf. If normal field,    M
  89. *                     NSrf, is prescribed, normal curves are concatenated    M
  90. *                     alternatingly in this list.                            M
  91. *                                                                            *
  92. * KEYWORDS:                                                                  M
  93. *   SymbAdapIsoExtract, adaptive isocurves                                   M
  94. *****************************************************************************/
  95. CagdCrvStruct *SymbAdapIsoExtract(CagdSrfStruct *Srf,
  96.                   CagdSrfStruct *NSrf,
  97.                   SymbAdapIsoDistSqrFuncType AdapIsoDistFunc,
  98.                   CagdSrfDirType Dir,
  99.                   CagdRType Eps,
  100.                   CagdBType FullIso,
  101.                   CagdBType SinglePath)
  102. {
  103.     CagdBType
  104.     SrfBezier = FALSE;
  105.     CagdRType Crv1Param, Crv2Param;
  106.     CagdCrvStruct *Crv1, *Crv2, *NCrv1, *NCrv2, *AllAdapIso, *TCrv;
  107.  
  108.     if (NSrf != NULL)
  109.     SinglePath = FALSE;
  110.  
  111.     switch (Srf -> GType) {
  112.     case CAGD_SBEZIER_TYPE:
  113.         Srf = CnvrtBezier2BsplineSrf(Srf);
  114.         SrfBezier = TRUE;
  115.         break;
  116.     case CAGD_SBSPLINE_TYPE:
  117.         break;
  118.     default:
  119.         SYMB_FATAL_ERROR(SYMB_ERR_WRONG_SRF);
  120.         break;
  121.     }
  122.  
  123.     switch (Dir) {
  124.     case CAGD_CONST_U_DIR:
  125.         Crv1Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  126.         Srf -> UKnotVector[0] + EPSILON : EPSILON;
  127.         Crv2Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  128.         Srf -> UKnotVector[Srf -> ULength +
  129.                    Srf -> UOrder - 1] - EPSILON
  130.         : 1.0 - EPSILON;
  131.         break;
  132.     case CAGD_CONST_V_DIR:
  133.         Crv1Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  134.         Srf -> VKnotVector[0] + EPSILON : EPSILON;
  135.         Crv2Param = Srf -> GType == CAGD_SBSPLINE_TYPE ? 
  136.         Srf -> VKnotVector[Srf -> VLength +
  137.                    Srf -> VOrder - 1] - EPSILON
  138.         : 1.0 - EPSILON;
  139.         break;
  140.     default:
  141.         SYMB_FATAL_ERROR(SYMB_ERR_DIR_NOT_CONST_UV);
  142.         Crv1Param = 0.0;
  143.         Crv2Param = 1.0;
  144.         break;
  145.     }
  146.  
  147.     Crv1 = CagdCrvFromSrf(Srf, Crv1Param, Dir);
  148.     Crv2 = CagdCrvFromSrf(Srf, Crv2Param, Dir);
  149.     if (NSrf != NULL) {
  150.     NCrv1 = CagdCrvFromSrf(NSrf, Crv1Param, Dir);
  151.     NCrv2 = CagdCrvFromSrf(NSrf, Crv2Param, Dir);
  152.     }
  153.     else
  154.     NCrv1 = NCrv2 = NULL;
  155.  
  156.     /* Compute the adaptive iso curves. */
  157.     AllAdapIso = SymbAdapIsoExtractAux(0, Srf, NSrf, AdapIsoDistFunc,
  158.                        Crv1, NCrv1, Crv2, NCrv2,
  159.                        Crv1Param, Crv2Param,
  160.                        Dir, Eps * Eps, FullIso, SinglePath);
  161.  
  162.     /* Chain first and last iso curves that always span the entire domain. */
  163.     if (AllAdapIso != NULL) {
  164.     Crv1 -> Pnext = AllAdapIso;
  165.     TCrv = CagdListLast(AllAdapIso);
  166.     TCrv -> Pnext = Crv2;
  167.     }
  168.     else
  169.     Crv1 -> Pnext = Crv2;
  170.  
  171.     if (NSrf != NULL) {
  172.     NCrv1 -> Pnext = Crv1 -> Pnext;
  173.     Crv1 -> Pnext = NCrv1;
  174.     NCrv2 -> Pnext = Crv2 -> Pnext;
  175.     Crv2 -> Pnext = NCrv2;
  176.     }
  177.  
  178.     if (SrfBezier)
  179.     CagdSrfFree(Srf);
  180.  
  181.     return Crv1;
  182. }
  183.  
  184. /*****************************************************************************
  185. * DESCRIPTION:                                                               *
  186. * An auxiliary function of SymbAdapIsoExtract. Computes the distance square  *
  187. * between the given two curves, extract the regions that are far than that   *
  188. * and recursively invoke this function with the sub-curves.             *
  189. *                                                                            *
  190. * PARAMETERS:                                                                *
  191. *   Level:         Of recursion.                                             *
  192. *   Srf:           This adaptive isocurve coverage is computed for.          *
  193. *   NSrf:          Normal vectorfield of Srf.                                *
  194. *   AdapIsoDistFunc: Optional function to invoke with the two adjacent       *
  195. *           isoparametric curves of the coverage to evaluate the      *
  196. *           distance between them.                     *
  197. *   Crv1:          First curve to handle.                                    *
  198. *   NCrv1:         Normal vector field of first curve Crv1.                  *
  199. *   Crv2:          Second curve to handle.                                   *
  200. *   NCrv2:         Normal vector field of second curve Crv2.                 *
  201. *   Crv1Param:     Parameter along the other direction of Srf, of Crv1.      *
  202. *   Crv2Param:     Parameter along the other direction of Srf, of Crv2.      *
  203. *   Dir:           Direction of adaptive isocurve extraction.                *
  204. *   Eps2:          Tolerance of adaptive isocurve extraction.                *
  205. *   FullIso:       Do we want all isocurves to span all parametric domain?   *
  206. *   SinglePath:    Do we want everything in a single path?                   *
  207. *                                                                            *
  208. * RETURN VALUE:                                                              *
  209. *   CagdCrvStruct *:  A list of isocurves covering Srf to within Eps2.       *
  210. *****************************************************************************/
  211. static CagdCrvStruct *SymbAdapIsoExtractAux(int Level,
  212.                         CagdSrfStruct *Srf,
  213.                         CagdSrfStruct *NSrf,
  214.                         SymbAdapIsoDistSqrFuncType
  215.                                           AdapIsoDistFunc,
  216.                         CagdCrvStruct *Crv1,
  217.                         CagdCrvStruct *NCrv1,
  218.                         CagdCrvStruct *Crv2,
  219.                         CagdCrvStruct *NCrv2,
  220.                         CagdRType Crv1Param,
  221.                         CagdRType Crv2Param,
  222.                         CagdSrfDirType Dir,
  223.                         CagdRType Eps2,
  224.                         CagdBType FullIso,
  225.                         CagdBType SinglePath)
  226. {
  227.     int i, KVLen;
  228.     CagdPointType PType;
  229.     CagdRType Dist, *KV, LastT, DistCrv2Min, DistCrv2Max,
  230.     **Points, *PtsW, *PtsX, LastDist,
  231.     *Nodes = NULL;
  232.     CagdBType CloseEnough, LastCloseEnough;
  233.     CagdCrvStruct *TCrv, *DistCrv2,
  234.     *AllAdapIsoTail = NULL,
  235.     *AllAdapIso = NULL;
  236.  
  237.     if (AdapIsoDistFunc != NULL) { /* Call function to compute distance sqr. */
  238.     DistCrv2 = AdapIsoDistFunc(Level, Crv1, NCrv1, Crv2, NCrv2);
  239.     }
  240.     else {           /* Symbolically compute the distance square function. */
  241.     CagdCrvStruct
  242.         *DiffCrv = SymbCrvSub(Crv1, Crv2);
  243.  
  244.     DistCrv2 = SymbCrvDotProd(DiffCrv, DiffCrv);
  245.     CagdCrvFree(DiffCrv);
  246.     }
  247.     PType = DistCrv2 -> PType;
  248.  
  249.     /* Simple heuristic how much to refine DistCrv2: */
  250.     KVLen = DistCrv2 -> Length * 2;
  251.     DistCrv2Min = DistCrv2 -> KnotVector[0];
  252.     DistCrv2Max = DistCrv2 -> KnotVector[DistCrv2 -> Order +
  253.                      DistCrv2 -> Length - 1];
  254.     KV = (CagdRType *) IritMalloc(sizeof(CagdRType) * KVLen);
  255.     for (i = 0; i < KVLen; i++)
  256.     KV[i] = DistCrv2Min + (i + 1) * (DistCrv2Max - DistCrv2Min) /
  257.                                 (KVLen + 1);
  258.  
  259.     TCrv = BspCrvKnotInsertNDiff(DistCrv2, FALSE, KV, KVLen);
  260.     IritFree((VoidPtr) KV);
  261.     CagdCrvFree(DistCrv2);
  262.     DistCrv2 = TCrv;
  263.  
  264.     Nodes = CagdCrvNodes(DistCrv2);
  265.     LastT = Nodes[0];
  266.     Points = DistCrv2 -> Points,
  267.     PtsW = Points[W],
  268.     PtsX = Points[X],
  269.     LastDist = (PType == CAGD_PT_E1_TYPE ? PtsX[0]
  270.                      : (PtsX[0] / PtsW[0])) - Eps2;
  271.     LastCloseEnough = LastDist < 0.0 && MinSubdivLevel <= Level;
  272.  
  273.     for (i = 1; i < DistCrv2 -> Length; i++) {
  274.     Dist = (PType == CAGD_PT_E1_TYPE ? PtsX[i]
  275.                      : (PtsX[i] / PtsW[i])) - Eps2;
  276.     CloseEnough = Dist < 0.0 && MinSubdivLevel <= Level;
  277.  
  278.     if (CloseEnough != LastCloseEnough ||
  279.         (i == DistCrv2 -> Length - 1 && !LastCloseEnough)) {
  280.         CagdRType t;
  281.         int KnotIndex,
  282.             KVLength = Crv1 -> Length + Crv1 -> Order;
  283.  
  284.         if (CloseEnough == LastCloseEnough)
  285.         t = Nodes[DistCrv2 -> Length - 1];
  286.         else
  287.         CONVEX_BLEND(Nodes[i - 1], Nodes[i], LastDist, Dist, t);
  288.  
  289.         /* If parameter t is close "enough" to an existing knot. use it. */
  290.         KnotIndex = BspKnotLastIndexLE(Crv1 -> KnotVector, KVLength, t);
  291.         if (KnotIndex >= 0 &&
  292.         t - Crv1 -> KnotVector[KnotIndex] < SIMILAR_PARAM_VAL)
  293.         t = Crv1 -> KnotVector[KnotIndex];
  294.         KnotIndex = BspKnotFirstIndexG(Crv1 -> KnotVector, KVLength, t);
  295.         if (KnotIndex < KVLength &&
  296.         Crv1 -> KnotVector[KnotIndex] - t < SIMILAR_PARAM_VAL)
  297.         t = Crv1 -> KnotVector[KnotIndex];
  298.  
  299.         if (t - LastT > SIMILAR_PARAM_VAL &&
  300.         (CloseEnough ||
  301.          (i == DistCrv2 -> Length - 1 && !LastCloseEnough))) {
  302.         /* We are at the end of a region that is not close enough. */
  303.         if (SinglePath) {
  304.             CagdRType
  305.                 MidParam1 = (Crv1Param * 2.0 + Crv2Param) / 3.0,
  306.             MidParam2 = (Crv1Param + Crv2Param * 2.0) / 3.0;
  307.             CagdCrvStruct
  308.                 *AdapIso1, *AdapIso2, *AdapIso3, *AdapIso,
  309.             *MidCrv1 = CagdCrvFromSrf(Srf, MidParam1, Dir),
  310.             *MidCrv2 = CagdCrvFromSrf(Srf, MidParam2, Dir);
  311.  
  312.             if (FullIso) {
  313.             AdapIso1 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  314.                              AdapIsoDistFunc,
  315.                              Crv1, NULL,
  316.                              MidCrv1, NULL,
  317.                              Crv1Param, MidParam1,
  318.                              Dir, Eps2,
  319.                              FullIso, SinglePath);
  320.             AdapIso2 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  321.                              AdapIsoDistFunc,
  322.                              MidCrv1, NULL,
  323.                              MidCrv2, NULL,
  324.                              MidParam1, MidParam2,
  325.                              Dir, Eps2,
  326.                              FullIso, SinglePath);
  327.             AdapIso3 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  328.                              AdapIsoDistFunc,
  329.                              MidCrv2, NULL,
  330.                              Crv2, NULL,
  331.                              MidParam2, Crv2Param,
  332.                              Dir, Eps2,
  333.                              FullIso, SinglePath);
  334.  
  335.             if (AdapIso1 != NULL) {
  336.                 for (TCrv = AdapIso1;
  337.                  TCrv -> Pnext != NULL;
  338.                  TCrv = TCrv -> Pnext);
  339.                 TCrv -> Pnext = MidCrv1;
  340.                 AdapIso = AdapIso1;
  341.             }
  342.             else
  343.                 AdapIso = MidCrv1; 
  344.             if (AdapIso2 != NULL)
  345.                 MidCrv1 -> Pnext = AdapIso2;
  346.  
  347.             if (AdapIso2 != NULL) {
  348.                 for (TCrv = AdapIso2;
  349.                  TCrv -> Pnext != NULL;
  350.                  TCrv = TCrv -> Pnext);
  351.                 TCrv -> Pnext = MidCrv2;
  352.             }
  353.             else
  354.                 MidCrv1 -> Pnext = MidCrv2;
  355.             if (AdapIso2 != NULL)
  356.                 MidCrv2 -> Pnext = AdapIso3;
  357.  
  358.             /* Chain these isolines to the entire set.*/
  359.             if (AllAdapIso)
  360.                 AllAdapIsoTail -> Pnext = AdapIso;
  361.             else
  362.                 AllAdapIso = AdapIso;
  363.  
  364.             for (AllAdapIsoTail = MidCrv2;
  365.                  AllAdapIsoTail -> Pnext != NULL;
  366.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  367.  
  368.             break; /* Only one (entire domain) region! */
  369.             }
  370.             else {
  371.             CagdCrvStruct *Region1, *Region2,
  372.                 *MidRegion1, *MidRegion2;
  373.  
  374.             Region1 = CopyRegionFromCrv(Crv1, LastT, t),
  375.             Region2 = CopyRegionFromCrv(Crv2, LastT, t);
  376.             MidRegion1 = CopyRegionFromCrv(MidCrv1, LastT, t);
  377.             MidRegion2 = CopyRegionFromCrv(MidCrv2, LastT, t);
  378.             CagdCrvFree(MidCrv1);
  379.             CagdCrvFree(MidCrv2);
  380.  
  381.             AdapIso1 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  382.                              AdapIsoDistFunc,
  383.                              Region1, NULL,
  384.                              MidRegion1, NULL,
  385.                              Crv1Param, MidParam1,
  386.                              Dir, Eps2,
  387.                              FullIso, SinglePath);
  388.             AdapIso2 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  389.                              AdapIsoDistFunc,
  390.                              MidRegion1, NULL,
  391.                              MidRegion2, NULL,
  392.                              MidParam1, MidParam2,
  393.                              Dir, Eps2,
  394.                              FullIso, SinglePath);
  395.             AdapIso3 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  396.                              AdapIsoDistFunc,
  397.                              MidRegion2, NULL,
  398.                              Region2, NULL,
  399.                              MidParam2, Crv2Param,
  400.                              Dir, Eps2,
  401.                              FullIso, SinglePath);
  402.  
  403.             if (AdapIso1 != NULL) {
  404.                 for (TCrv = AdapIso1;
  405.                  TCrv -> Pnext != NULL;
  406.                  TCrv = TCrv -> Pnext);
  407.                 TCrv -> Pnext = MidRegion1;
  408.                 AdapIso = AdapIso1;
  409.             }
  410.             else
  411.                 AdapIso = MidRegion1; 
  412.             if (AdapIso2 != NULL)
  413.                 MidRegion1 -> Pnext = AdapIso2;
  414.  
  415.             if (AdapIso2 != NULL) {
  416.                 for (TCrv = AdapIso2;
  417.                  TCrv -> Pnext != NULL;
  418.                  TCrv = TCrv -> Pnext);
  419.                 TCrv -> Pnext = MidRegion2;
  420.             }
  421.             else
  422.                 MidRegion1 -> Pnext = MidRegion2;
  423.             if (AdapIso2 != NULL)
  424.                 MidRegion2 -> Pnext = AdapIso3;
  425.  
  426.             /* Chain these isolines to the entire set.*/
  427.             if (AllAdapIso)
  428.                 AllAdapIsoTail -> Pnext = AdapIso;
  429.             else
  430.                 AllAdapIso = AdapIso;
  431.  
  432.             for (AllAdapIsoTail = MidRegion2;
  433.                  AllAdapIsoTail -> Pnext != NULL;
  434.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  435.             }
  436.         }
  437.         else { /* Return all the isocurves as a list of curves. */
  438.             CagdRType
  439.                 MidParam = ComputeMidParam(Crv1Param, Crv2Param,
  440.                            Dir, Srf);
  441.             CagdCrvStruct *AdapIso1, *AdapIso2, *AdapIso,
  442.             *MidCrv = CagdCrvFromSrf(Srf, MidParam, Dir),
  443.             *MidNCrv = NSrf ? CagdCrvFromSrf(NSrf, MidParam, Dir)
  444.                     : NULL;
  445.  
  446.             if (FullIso) {
  447.             AdapIso1 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  448.                              AdapIsoDistFunc,
  449.                              Crv1, NCrv1,
  450.                              MidCrv, MidNCrv,
  451.                              Crv1Param, MidParam,
  452.                              Dir, Eps2,
  453.                              FullIso, SinglePath);
  454.             AdapIso2 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  455.                              AdapIsoDistFunc,
  456.                              MidCrv, MidNCrv,
  457.                              Crv2, NCrv2,
  458.                              MidParam, Crv2Param,
  459.                              Dir, Eps2,
  460.                              FullIso, SinglePath);
  461.  
  462.             if (AdapIso1 != NULL) {
  463.                 for (TCrv = AdapIso1;
  464.                  TCrv -> Pnext != NULL;
  465.                  TCrv = TCrv -> Pnext);
  466.                 TCrv -> Pnext = MidCrv;
  467.                 AdapIso = AdapIso1;
  468.             }
  469.             else
  470.                 AdapIso = MidCrv;
  471.  
  472.             if (NSrf != NULL) {
  473.                 MidCrv -> Pnext = MidNCrv;
  474.                 MidCrv = MidNCrv;
  475.             }
  476.  
  477.             if (AdapIso2 != NULL)
  478.                 MidCrv -> Pnext = AdapIso2;
  479.  
  480.             /* Chain these isolines to the entire set.*/
  481.             if (AllAdapIso)
  482.                 AllAdapIsoTail -> Pnext = AdapIso;
  483.             else
  484.                 AllAdapIso = AdapIso;
  485.  
  486.             for (AllAdapIsoTail = MidCrv;
  487.                  AllAdapIsoTail -> Pnext != NULL;
  488.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  489.  
  490.             break; /* Only one (entire domain) region! */
  491.             }
  492.             else {
  493.             CagdCrvStruct *Region1, *Region2, *MidRegion,
  494.                 *NRegion1 = NULL,
  495.                 *NRegion2 = NULL,
  496.                 *MidNRegion = NULL;
  497.  
  498.             Region1 = CopyRegionFromCrv(Crv1, LastT, t);
  499.             Region2 = CopyRegionFromCrv(Crv2, LastT, t);
  500.             MidRegion = CopyRegionFromCrv(MidCrv, LastT, t);
  501.             if (NSrf) {
  502.                 NRegion1 = CopyRegionFromCrv(NCrv1, LastT, t);
  503.                 NRegion2 = CopyRegionFromCrv(NCrv2, LastT, t);
  504.                 MidNRegion = CopyRegionFromCrv(MidNCrv, LastT,
  505.                                   t);
  506.                 CagdCrvFree(MidNCrv);
  507.             }
  508.             CagdCrvFree(MidCrv);
  509.  
  510.             AdapIso1 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  511.                              AdapIsoDistFunc,
  512.                              Region1, NRegion1,
  513.                              MidRegion, MidNRegion,
  514.                              Crv1Param, MidParam,
  515.                              Dir, Eps2,
  516.                              FullIso, SinglePath);
  517.             AdapIso2 = SymbAdapIsoExtractAux(Level + 1, Srf, NSrf,
  518.                              AdapIsoDistFunc,
  519.                              MidRegion, MidNRegion,
  520.                              Region2, NRegion2,
  521.                              MidParam, Crv2Param,
  522.                              Dir, Eps2,
  523.                              FullIso, SinglePath);
  524.  
  525.             if (AdapIso1 != NULL) {
  526.                 for (TCrv = AdapIso1;
  527.                  TCrv -> Pnext != NULL;
  528.                  TCrv = TCrv -> Pnext);
  529.                 TCrv -> Pnext = MidRegion;
  530.                 AdapIso = AdapIso1;
  531.             }
  532.             else
  533.                 AdapIso = MidRegion;
  534.  
  535.             if (NSrf != NULL) {
  536.                 MidRegion -> Pnext = MidNRegion;
  537.                 MidRegion = MidNRegion;
  538.             }
  539.  
  540.             if (AdapIso2 != NULL)
  541.                 MidRegion -> Pnext = AdapIso2;
  542.  
  543.             CagdCrvFree(Region1);
  544.             CagdCrvFree(Region2);
  545.             if (NSrf != NULL) {
  546.                 CagdCrvFree(NRegion1);
  547.                 CagdCrvFree(NRegion2);
  548.             }
  549.  
  550.             /* Chain these isolines to the entire set.*/
  551.             if (AllAdapIso)
  552.                 AllAdapIsoTail -> Pnext = AdapIso;
  553.             else
  554.                 AllAdapIso = AdapIso;
  555.  
  556.             for (AllAdapIsoTail = MidRegion;
  557.                  AllAdapIsoTail -> Pnext != NULL;
  558.                  AllAdapIsoTail = AllAdapIsoTail -> Pnext);
  559.             }
  560.         }
  561.         }
  562.  
  563.         /* We are at the beginning of a region not close enough. */
  564.         LastT = t;
  565.     }
  566.  
  567.     LastDist = Dist;
  568.     LastCloseEnough = CloseEnough;
  569.     }
  570.  
  571.     CagdCrvFree(DistCrv2);
  572.     IritFree((VoidPtr) Nodes);
  573.  
  574.     if (SinglePath) { /* Add connecting isocurves into the existing curves. */
  575.     /* Not implemented yet. */
  576.     }
  577.  
  578.     return AllAdapIso;
  579. }
  580.  
  581. /*****************************************************************************
  582. * DESCRIPTION:                                                               *
  583. *   Extracts a sub region of the given curve, but also copies its attributes.*
  584. *                                                                            *
  585. * PARAMETERS:                                                                *
  586. *   Crv:        To extracts a region from.                                   *
  587. *   TMin, TMax: Domain of region.                                            *
  588. *                                                                            *
  589. * RETURN VALUE:                                                              *
  590. *   CagdCrvStruct *:   Extracted region.                                     *
  591. *****************************************************************************/
  592. static CagdCrvStruct *CopyRegionFromCrv(CagdCrvStruct *Crv,
  593.                     CagdRType TMin,
  594.                     CagdRType TMax)
  595. {
  596.     CagdCrvStruct
  597.     *Region = CagdCrvRegionFromCrv(Crv, TMin, TMax);
  598.  
  599.     Region -> Attr = AttrCopyAttributes(Crv -> Attr);
  600.  
  601.     return Region;
  602. }
  603.  
  604.  
  605. /*****************************************************************************
  606. * DESCRIPTION:                                                               *
  607. *   Estimates a parameter between Param1 and Param2 inSrf in Dir. Selects    *
  608. * interior knots before selecting an average between parameters.             *
  609. *                                                                            *
  610. * PARAMETERS:                                                                *
  611. *   Param1, Param2:  Two parameters to find in between.                      *
  612. *   Dir:             Direction in Srf of Param1/2.                           *
  613. *   Srf:             Surface to explore.                                     *
  614. *                                                                            *
  615. * RETURN VALUE:                                                              *
  616. *   CagdRType:       A parameter between Param1 and Param2.                  *
  617. *****************************************************************************/
  618. static CagdRType ComputeMidParam(CagdRType Param1,
  619.                  CagdRType Param2,
  620.                  CagdSrfDirType Dir,
  621.                  CagdSrfStruct *Srf)
  622. {
  623.     CagdRType t, *KV;
  624.     int KVLen, Index1, Index2;
  625.  
  626.     switch (Dir) {
  627.     case CAGD_CONST_U_DIR:
  628.         KV = Srf -> UKnotVector;
  629.         KVLen = Srf -> UOrder + Srf -> ULength;
  630.         break;
  631.     case CAGD_CONST_V_DIR:
  632.         KV = Srf -> VKnotVector;
  633.         KVLen = Srf -> VOrder + Srf -> VLength;
  634.         break;
  635.     default:
  636.         SYMB_FATAL_ERROR(SYMB_ERR_DIR_NOT_CONST_UV);
  637.         KV = NULL;
  638.         KVLen = 0;
  639.     }
  640.  
  641.     Index1 = BspKnotLastIndexLE(KV, KVLen, Param1);
  642.     Index2 = BspKnotLastIndexLE(KV, KVLen, Param2);
  643.  
  644.     if (Index1 < 0 || Index2 < 0 || Index1 >= KVLen || Index2 >= KVLen) {
  645.     SYMB_FATAL_ERROR(SYMB_ERR_OUT_OF_RANGE);
  646.     return -INFINITY;
  647.     }
  648.  
  649.     t = KV[(Index1 + Index2) / 2];
  650.     if (t < Param1 || t > Param2 || APX_EQ(t, Param1) || APX_EQ(t, Param2))
  651.     t = (Param1 + Param2) / 2.0;
  652.  
  653.     return t;
  654. }
  655.  
  656.